﻿/************************************************************************

   Extended Silverlight Toolkit

   Copyright (C) 2010-2012 Xceed Software Inc.

   This program is provided to you under the terms of the Microsoft Public
   License (Ms-PL) as published at http://extendedsilverlight.codeplex.com/license

   Please purchase a commercial version of this toolkit if you are using
   it in a commercial product. The commercial versions support the project,
   and also include more features for each control, priority support,
   source code, updates, removed watermark, and a proprietary license.

   Visit http://xceed.com and follow @datagrid on Twitter.

  **********************************************************************/

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Linq;

namespace Xceed.Silverlight.Data
{
  internal abstract class CacheEnumerator : AsyncParentEnumerator<DataPath>, ICachingEnumerator
  {
    #region Static Fields

    private static readonly Guid JumpMoveAndFetchCallId = DataUtils.CreateCallId();
    private static readonly Guid GetStatValuesCallId = DataUtils.CreateCallId();

    #endregion

    #region Constructor

    protected CacheEnumerator(
      IAsyncEnumerator<DataPath> childEnumerator,
      IContextualCompareHelper compareHelper,
      IContextualItemHelper itemHelper,
      int cacheSize )
      : base( childEnumerator )
    {
      if( compareHelper == null )
        throw new ArgumentNullException( "compareHelper" );

      if( itemHelper == null )
        throw new ArgumentNullException( "itemHelper" );

      if( cacheSize < 0 )
        throw new ArgumentOutOfRangeException( "cacheSize", "cacheSize must be greater than or equal to zero." );

      m_compareHelper = compareHelper;
      m_itemHelper = itemHelper;
      m_cacheSize = cacheSize;
    }

    #endregion

    #region IsCacheAtStart Protected Property

    protected bool IsCacheAtStart
    {
      get
      {
        lock( this.SyncRoot )
        {
          return ( this.CalculateCacheLimitPosition( true ) == CachePositionState.Yes );
        }
      }
    }

    #endregion

    #region IsCacheAtEnd Protected Property

    protected bool IsCacheAtEnd
    {
      get
      {
        lock( this.SyncRoot )
        {
          return ( this.CalculateCacheLimitPosition( false ) == CachePositionState.Yes );
        }
      }
    }

    #endregion

    #region CompareHelper Protected Property

    protected IContextualCompareHelper CompareHelper
    {
      get
      {
        return m_compareHelper;
      }
    }

    private readonly IContextualCompareHelper m_compareHelper;

    #endregion

    #region ItemHelper Protected Property

    protected IContextualItemHelper ItemHelper
    {
      get
      {
        return m_itemHelper;
      }
    }

    private readonly IContextualItemHelper m_itemHelper;

    #endregion

    #region CacheSize Property

    internal int CacheSize
    {
      get
      {
        lock( this.SyncRoot )
        {
          return m_cacheSize;
        }
      }
      private set
      {
        lock( this.SyncRoot )
        {
          m_cacheSize = value;
        }
      }
    }

    private int m_cacheSize;

    #endregion

    #region CachedItems Property

    internal List<DataPath> CachedItems
    {
      get
      {
        return m_cachedItems;
      }
    }

    private List<DataPath> m_cachedItems = new List<DataPath>();

    #endregion

    #region TotalItemCount Property

    internal EstimateInt64 TotalItemCount
    {
      get
      {
        lock( this.SyncRoot )
        {
          return m_totalItemCount;
        }
      }
      set
      {
        lock( this.SyncRoot )
        {
          m_totalItemCount = value;
        }
      }
    }

    private EstimateInt64 m_totalItemCount; //null

    #endregion

    #region CachedStatResults Property

    internal IDictionary<StatParameters, StatResults> CachedStatResults
    {
      get
      {
        return m_cachedStatResults;
      }
    }

    private Dictionary<StatParameters, StatResults> m_cachedStatResults = new Dictionary<StatParameters, StatResults>();

    #endregion

    #region ReferencePosition Property

    internal RelativeOffset FirstItemOffset
    {
      get
      {
        return m_firstItemOffset;
      }
    }

    private RelativeOffset m_firstItemOffset = null;

    #endregion

    #region IsCacheComplete Property

    private bool IsCacheComplete
    {
      get
      {
        lock( this.SyncRoot )
        {
          return ( this.IsCacheAtStart && this.IsCacheAtEnd );
        }
      }
    }

    #endregion

    protected abstract DataSourceContext GetCurrentContext();

    protected DataSourceContext GetContext( JumpMoveAndFetchParameters parameters )
    {
      DataSourceContext context = parameters.Context;

      if( context == null )
      {
        context = this.GetCurrentContext();
      }

      return context;
    }

    protected DataSourceContext GetContext( StatParameters parameters )
    {
      DataSourceContext context = parameters.Context;

      if( context == null )
      {
        context = this.GetCurrentContext();
      }

      return context;
    }

    protected bool MatchCurrentContext( DataSourceContext context )
    {
      return object.Equals( context, this.GetCurrentContext() );
    }

    internal void InvalidateCountInformation( bool beforeFirstToFirstItemReliable = false )
    {
      bool invalidateFirstItemOffset = true;
      if( beforeFirstToFirstItemReliable && ( m_firstItemOffset != null ) )
      {
        invalidateFirstItemOffset = ( m_firstItemOffset.ReferencePosition != ReferencePoint.BeforeFirst );
      }

      if( invalidateFirstItemOffset )
      {
        m_firstItemOffset = m_firstItemOffset.ToEstimate();
      }

      m_totalItemCount = m_totalItemCount.ToEstimate();

      this.UpdateCountInformation( m_firstItemOffset, m_totalItemCount );
    }

    internal void UpdateCountInformation( RelativeOffset firstItemOffset, EstimateInt64 totalCount )
    {
      lock( this.SyncRoot )
      {
        if( ( firstItemOffset != null && m_firstItemOffset != null )
          && ( firstItemOffset.ReferencePosition != m_firstItemOffset.ReferencePosition ) )
        {

          if( totalCount == null
            || ( totalCount.IsEstimate && !firstItemOffset.IsEstimate && !m_firstItemOffset.IsEstimate ) )
          {
            totalCount = firstItemOffset.EstimateValue + m_firstItemOffset.EstimateValue;
            totalCount -= 1;
          }
        }

        bool isRealReference = ( firstItemOffset != null ) && ( !firstItemOffset.IsEstimate );
        bool isRealTotal = ( totalCount != null ) && ( !totalCount.IsEstimate );

        if( isRealTotal )
        {
          m_totalItemCount = totalCount;
        }

        if( isRealReference )
        {
          m_firstItemOffset = firstItemOffset;
        }

        if( isRealReference )
        {
          EstimateInt64 otherReference =
            ( m_totalItemCount != null && !m_totalItemCount.IsEstimate )
            ? m_totalItemCount.Value - m_firstItemOffset.Value + 1
            : ( EstimateInt64 )null;

          EstimateInt64 beforeFirstReference =
            ( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst )
            ? m_firstItemOffset.EstimateValue
            : otherReference;

          EstimateInt64 afterLastReference =
            ( m_firstItemOffset.ReferencePosition == ReferencePoint.AfterLast )
            ? m_firstItemOffset.EstimateValue
            : otherReference;

          if( beforeFirstReference != null && beforeFirstReference.Value <= 0 )
          {
            int removeItemCount = Convert.ToInt32( -beforeFirstReference.Value + 1 );


            m_cachedItems.RemoveRange( 0, removeItemCount );

            m_firstItemOffset = DataUtils.CalculateRelativeOffset( m_firstItemOffset, removeItemCount );

            firstItemOffset = DataUtils.CalculateRelativeOffset( firstItemOffset, removeItemCount );
          }

          if( afterLastReference != null && ( afterLastReference.Value < m_cachedItems.Count ) )
          {
            int removeItemCount = Convert.ToInt32( m_cachedItems.Count - afterLastReference.Value );



            m_cachedItems.RemoveRange(
              Convert.ToInt32( m_cachedItems.Count - removeItemCount ),
              removeItemCount );
          }
        }

        if( isRealTotal && m_totalItemCount.Value < m_cachedItems.Count )
        {
          Debug.Assert( m_firstItemOffset == null || m_firstItemOffset.IsEstimate,
            "This should have been handled in the previous if" );
          Debug.Assert( false );
        }

        if( firstItemOffset != null )
        {
          if( ( ( firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst ) && firstItemOffset.Value <= 0 )
            || ( ( firstItemOffset.ReferencePosition == ReferencePoint.AfterLast ) && firstItemOffset.Value < m_cachedItems.Count ) )
          {
            Debug.Assert( firstItemOffset.IsEstimate );
            firstItemOffset = m_firstItemOffset;
          }
        }

        if( totalCount != null && totalCount.Value < m_cachedItems.Count )
        {
          Debug.Assert( totalCount.IsEstimate );
          totalCount = m_totalItemCount;
        }

        bool isCacheAtStart = this.IsCacheAtStart;
        bool isCacheAtEnd = this.IsCacheAtEnd;

        bool newCacheAtStart = CacheEnumerator.CalculateCacheLimitPosition(
          true,
          m_cachedItems.Count,
          firstItemOffset,
          totalCount ) == CachePositionState.Yes;

        bool newCacheAtEnd = CacheEnumerator.CalculateCacheLimitPosition(
          false,
          m_cachedItems.Count,
          firstItemOffset,
          totalCount ) == CachePositionState.Yes;

        if( isCacheAtStart && !newCacheAtStart )
        {
          firstItemOffset = null;
          if( m_firstItemOffset.ReferencePosition == ReferencePoint.AfterLast )
          {
            totalCount = null;
          }
        }

        if( isCacheAtEnd && !newCacheAtEnd )
        {
          firstItemOffset = null;
          if( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst )
          {
            totalCount = null;
          }
        }

        if( firstItemOffset != null )
        {
          m_firstItemOffset = firstItemOffset;
        }

        if( totalCount != null )
        {
          m_totalItemCount = totalCount;
        }
      }
    }

    private CachePositionState CalculateCacheLimitPosition( bool atStartPosition )
    {
      lock( this.SyncRoot )
      {
        return CacheEnumerator.CalculateCacheLimitPosition(
          atStartPosition,
          m_cachedItems.Count,
          m_firstItemOffset,
          m_totalItemCount );
      }
    }

    private static CachePositionState CalculateCacheLimitPosition(
      bool atStartPosition,
      int cacheCount,
      RelativeOffset offset,
      EstimateInt64 totalCount )
    {
      EstimateInt64 limitOffset = CacheEnumerator.CalculateLimitOffset( atStartPosition, offset, totalCount );

      CachePositionState state = CachePositionState.Maybe;

      if( limitOffset != null && !limitOffset.IsEstimate )
      {
        if( atStartPosition )
        {
          state = ( limitOffset.Value <= 1 )
            ? CachePositionState.Yes
            : CachePositionState.No;
        }
        else
        {
          state = ( limitOffset.Value <= cacheCount )
            ? CachePositionState.Yes
            : CachePositionState.No;
        }
      }
      else if( ( cacheCount == 0 ) && ( totalCount == 0 ) )
      {
        state = CachePositionState.Yes;
      }

      return state;
    }

    private static EstimateInt64 CalculateLimitOffset(
      bool beforeFirstOffset,
      RelativeOffset providedOffset,
      EstimateInt64 totalCount )
    {
      EstimateInt64 offset = null;

      if( providedOffset != null )
      {
        if( ( ( providedOffset.ReferencePosition == ReferencePoint.BeforeFirst ) && beforeFirstOffset )
          || ( ( providedOffset.ReferencePosition != ReferencePoint.BeforeFirst ) && !beforeFirstOffset ) )
        {
          offset = providedOffset.EstimateValue;
        }
        else if( totalCount != null )
        {
          offset = ( totalCount - providedOffset.EstimateValue ) + 1;
        }
      }

      return offset;
    }

    #region Begin/End GetStatValues

    public override IAsyncResult BeginGetStatValues( StatParameters parameters, AsyncCallback userCallback, object asyncState )
    {
      DataSourceContext context = this.GetContext( parameters );
      parameters = new StatParameters(
                     parameters.StatFunctions,
                     parameters.TargetPath,
                     context );

      ContextAsyncResult asyncResult = new ContextAsyncResult( CacheEnumerator.GetStatValuesCallId, userCallback, asyncState );
      asyncResult.CallContext = parameters;

      StatResults results;
      bool resultsFound;

      lock( this.SyncRoot )
      {
        resultsFound = m_cachedStatResults.TryGetValue( parameters, out results );
      }

      if( resultsFound )
      {
        asyncResult.StartSync( results );
      }
      else
      {
        asyncResult.Start(
          ( callback, state ) => base.BeginGetStatValues( parameters, callback, state ),
            ( parentAr, childAr ) => new DependentCallResult( base.EndGetStatValues( childAr ) ) );
      }
      return asyncResult;
    }

    public override StatResults EndGetStatValues( IAsyncResult asyncResult )
    {
      asyncResult.ValidateCallEnd( CacheEnumerator.GetStatValuesCallId );
      StatResults results = asyncResult.GetCallResult<StatResults>();
      StatParameters parameters = ( StatParameters )( ( ContextAsyncResult )asyncResult ).CallContext;

      lock( this.SyncRoot )
      {
        if( !m_cachedStatResults.ContainsKey( parameters ) )
        {
          m_cachedStatResults.Add( parameters, results );
        }
      }

      return results;
    }

    #endregion

    #region Begin/End JumpMoveAndFetch

    public override JumpMoveAndFetchAsyncResult BeginJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      AsyncCallback userCallback,
      object asyncState )
    {
      this.CheckMoveAndFetchParameters(
        parameters.ExpectedMoveCount,
        parameters.ExpectedFetchCount );

      DataSourceContext context = this.GetContext( parameters );
      parameters = parameters.CreateWithNewContext( context );

      CacheJumpAsyncResult cacheAsyncResult = new CacheJumpAsyncResult(
                                               CacheEnumerator.JumpMoveAndFetchCallId,
                                               userCallback,
                                               asyncState,
                                               parameters );

      long actualMove;
      IList<DataPath> cacheData;
      SourcePosition endPosition;
      bool operationCompleted;
      Nullable<int> sourcePositionIndex;
      RelativeOffset endPositionOffset;
      EstimateInt64 totalCount;
      bool result;

      lock( this.SyncRoot )
      {
        this.InvalidateCountInformation( this.IsCacheAtStart );

        result = this.CacheJumpMoveAndFetch(
                   parameters,
                   out actualMove,
                   out cacheData,
                   out endPosition,
                   out sourcePositionIndex,
                   out operationCompleted,
                   out endPositionOffset,
                   out totalCount );
      }

      if( operationCompleted )
      {
        Debug.Assert( endPosition != null );

        cacheAsyncResult.StartSync(
          new JumpMoveAndFetchResult<DataPath>(
            cacheAsyncResult,
            actualMove,
            cacheData,
            result,
            endPosition,
            endPositionOffset,
            totalCount ) );
      }
      else
      {
        Debug.Assert( cacheData == null || cacheData.Count != 0 );

        long childMove = parameters.ExpectedMoveCount;
        int childFetch = parameters.ExpectedFetchCount;
        bool childApproximateMove = parameters.ApproximateMove;
        SourcePosition childFetchStart = parameters.SourcePosition;

        if( cacheData != null )
        {
          Debug.Assert( actualMove == parameters.ExpectedMoveCount );

          int fetchUnit = DataUtils.GetUnit( cacheAsyncResult.ExpectedFetchCount );

          childMove = fetchUnit;
          childFetch -= ( cacheData.Count * fetchUnit );
          childFetchStart = endPosition;
        }
        else if( actualMove != 0 )
        {
          Debug.Assert( m_cachedItems.Count != 0 );

          childMove -= actualMove;
          childFetchStart = endPosition;
        }

        cacheAsyncResult.CacheData = cacheData;
        cacheAsyncResult.CacheMove = actualMove;
        cacheAsyncResult.CacheEndPositionOffset = endPositionOffset;
        cacheAsyncResult.CacheTotalCount = totalCount;

        cacheAsyncResult.Start(
          ( callback, state ) => this.BeginChildJumpMoveAndFetch(
                                   new JumpMoveAndFetchParameters(
                                     childFetchStart,
                                     childMove,
                                     childFetch,
                                     childApproximateMove,
                                     context ),
                                   callback,
                                   state ),
          null );

        return cacheAsyncResult;
      }

      return cacheAsyncResult;
    }

    protected virtual JumpMoveAndFetchAsyncResult BeginChildJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      AsyncCallback userCallback,
      object asyncState )
    {
      return this.ChildEnumeratorTyped.BeginJumpMoveAndFetch(
        parameters,
        userCallback,
        asyncState );
    }

    private JumpMoveAndFetchResult<DataPath> CombineResults( CacheJumpAsyncResult cacheAsyncResult, JumpMoveAndFetchResult<DataPath> childResult )
    {
      Debug.Assert( childResult.GetFetchUnit() == cacheAsyncResult.GetFetchUnit() );

      List<DataPath> fetchedData = cacheAsyncResult.CacheData as List<DataPath>;
      Nullable<long> actualMove = null;
      ICollection<DataPath> fetchedItems = null;

      if( fetchedData == null && cacheAsyncResult.CacheData != null )
      {
        fetchedData = new List<DataPath>( cacheAsyncResult.CacheData );
      }

      Debug.Assert( ( ( fetchedData != null ) && childResult.ExpectedMoveCount == cacheAsyncResult.GetFetchUnit() )
        || ( ( fetchedData == null ) && childResult.GetMoveUnit() == cacheAsyncResult.GetMoveUnit() ) );

      if( cacheAsyncResult.CacheMove != cacheAsyncResult.ExpectedMoveCount )
      {
        if( childResult.ActualMoveCount.HasValue )
        {
          actualMove = cacheAsyncResult.CacheMove + childResult.ActualMoveCount.Value;
        }
      }
      else
      {
        actualMove = cacheAsyncResult.CacheMove;
      }

      if( fetchedData != null )
      {
        if( childResult.FetchedItems != null )
        {
          fetchedData.AddRange( childResult.FetchedItems );
        }

        fetchedItems = fetchedData;
      }
      else
      {
        fetchedItems = childResult.FetchedItems;
      }

      RelativeOffset endPositionOffset = null;
      EstimateInt64 totalCount = null;

      if( childResult.EndPositionOffset == null )
      {
        Debug.Assert( childResult.ActualMoveCount.HasValue, "Child should return a reference position if the move failed" );

        long offset = childResult.GetFetchDisplacement();

        offset += ( cacheAsyncResult.CacheMove != childResult.ActualMoveCount.Value )
          ? childResult.ActualMoveCount.Value
          : childResult.GetFetchUnit();

        endPositionOffset = DataUtils.CalculateRelativeOffset( cacheAsyncResult.CacheEndPositionOffset, offset );
      }
      else
      {
        endPositionOffset = childResult.EndPositionOffset;
      }

      if( childResult.TotalCount != null )
      {
        totalCount = childResult.TotalCount;
      }
      else
      {
        totalCount = cacheAsyncResult.CacheTotalCount;
      }

      return new JumpMoveAndFetchResult<DataPath>(
        cacheAsyncResult,
        actualMove,
        fetchedItems,
        childResult.Result,
        childResult.EndPositionObject,
        endPositionOffset,
        totalCount );
    }

    public override JumpMoveAndFetchResult<DataPath> EndJumpMoveAndFetch( JumpMoveAndFetchAsyncResult jumpMoveAndFetchAsyncResult )
    {
      if( m_disposed )
        return null;

      jumpMoveAndFetchAsyncResult.ValidateCallEnd( CacheEnumerator.JumpMoveAndFetchCallId );

      CacheJumpAsyncResult cacheAsyncResult = ( CacheJumpAsyncResult )jumpMoveAndFetchAsyncResult;

      JumpMoveAndFetchResult<DataPath> cacheOnlyOperationResult = cacheAsyncResult.GetCallResult<JumpMoveAndFetchResult<DataPath>>();

      //It will be started synchronously if all data was extracted from the cache.
      //No need to merge it.
      if( cacheOnlyOperationResult != null )
        return cacheOnlyOperationResult;

      JumpMoveAndFetchResult<DataPath> childResult = this.ChildEnumeratorTyped.EndJumpMoveAndFetch( ( JumpMoveAndFetchAsyncResult )cacheAsyncResult.LastIAsyncResult );

      lock( this.SyncRoot )
      {
        if( this.MergeResult( cacheAsyncResult.Context, childResult ) )
        {
          if( childResult.FetchedItems != null && childResult.FetchedItems.Count != 0 )
          {
            int topLimitIndex =
              jumpMoveAndFetchAsyncResult.IsFetchingForward()
              ? m_cachedItems.Count - 1
              : 0;

            this.TrimCache( topLimitIndex );
          }
        }
      }

      return this.CombineResults( cacheAsyncResult, childResult );
    }

    #endregion

    protected bool CacheJumpMoveAndFetch(
      JumpMoveAndFetchParameters parameters,
      out long actualMoveCount,
      out IList<DataPath> fetchedItems,
      out SourcePosition endPosition,
      out Nullable<int> sourcePositionIndex,
      out bool complete,
      out RelativeOffset endPositionOffset,
      out EstimateInt64 totalCount )
    {
      SourcePosition sourcePosition = parameters.SourcePosition;
      long expectedMoveCount = parameters.ExpectedMoveCount;
      int expectedFetchCount = parameters.ExpectedFetchCount;
      DataSourceContext context = this.GetContext( parameters );

      bool result;

      sourcePositionIndex = null;

      lock( this.SyncRoot )
      {
        if( this.MatchCurrentContext( context ) )
        {
          sourcePositionIndex = this.FindIndex( context, sourcePosition, expectedMoveCount, expectedFetchCount );
        }

        if( !sourcePositionIndex.HasValue || ( m_cachedItems.Count == 0 && !this.IsCacheComplete ) )
        {
          actualMoveCount = 0;
          fetchedItems = null;
          endPosition = sourcePosition;
          result = true;
          complete = false;
          endPositionOffset = null;
          totalCount = m_totalItemCount;
        }
        else
        {
          //Get the available data in cache.
          result = this.FetchCacheData(
                     sourcePositionIndex.Value,
                     expectedMoveCount,
                     expectedFetchCount,
                     out actualMoveCount,
                     out fetchedItems,
                     out endPosition,
                     out endPositionOffset,
                     out totalCount );

          if( endPosition == null )
          {
            Debug.Assert( actualMoveCount == 0 );
            Debug.Assert( fetchedItems == null );
            endPosition = sourcePosition;
            complete = false;
          }
          else
          {
            complete = endPosition.IsOutOfBound;
            complete = complete || ( fetchedItems != null ) && ( fetchedItems.Count == Math.Abs( expectedFetchCount ) );
          }
        }
      }

      return result;
    }

    protected virtual void ChildDataRemoved( DataPath oldItem, SourcePosition removePosition )
    {
      lock( this.SyncRoot )
      {
        Nullable<int> index = null;

        if( m_cachedItems.Count > 0 )
        {
          DataSourceContext context = this.GetCurrentContext();

          index = this.GetRemoveIndex( context, oldItem );
        }

        this.HandleItemChangeCore( true, index, false, null, null );
      }
    }

    protected virtual void ChildDataAdded( DataPath newItem )
    {
      lock( this.SyncRoot )
      {
        Nullable<int> index = null;

        if( m_cachedItems.Count > 0 )
        {
          DataSourceContext context = this.GetCurrentContext();

          index = this.GetInsertIndex( context, newItem );
        }

        this.HandleItemChangeCore( false, null, true, index, newItem );
      }
    }

    protected virtual void ChildDataReseted()
    {
      lock( this.SyncRoot )
      {
        m_cachedItems.Clear();
        this.ClearItemCountEstimates();
        m_totalItemCount = m_totalItemCount.ToEstimate();
      }
    }

    protected virtual void ChildDataReplaced( DataPath oldItem, DataPath newItem )
    {
      Nullable<int> removeIndex = null;
      Nullable<int> insertIndex = null;

      lock( this.SyncRoot )
      {
        if( m_cachedItems.Count > 0 )
        {
          DataSourceContext context = this.GetCurrentContext();

          removeIndex = this.GetRemoveIndex( context, oldItem );
          insertIndex = this.GetInsertIndex( context, newItem );
        }

        this.HandleItemChangeCore( true, removeIndex, true, insertIndex, newItem );
      }
    }

    protected virtual void ChildDataItemChanged( ItemChangedInfo itemChangedInfo )
    {
      if( itemChangedInfo == null )
        throw new ArgumentNullException( "itemChangedInfo" );

      DataSourceContext context = this.GetCurrentContext();

      if( !context.GetCurrentCompleteSortOrder().Any( itemChangedInfo.GetIsValueChanged ) )
        return;

      Nullable<int> removeIndex = null;
      Nullable<int> insertIndex = null;

      DataPath item = ( DataPath )itemChangedInfo.Target;

      lock( this.SyncRoot )
      {
        if( m_cachedItems.Count > 0 )
        {
          removeIndex = this.GetModifiedItemIndexInfo( context, itemChangedInfo );
          insertIndex = this.GetInsertIndex( context, item );
        }

        //A property changed on a sorted field is much like a "Replace" of the item with it's old value
        //for the item with the new value.
        this.HandleItemChangeCore( true, removeIndex, true, insertIndex, item );
      }
    }

    protected override void ChildDataChanged( DataChangedEventArgs args )
    {
      if( args.Action == DataChangedAction.Remove )
      {
        this.ChildDataRemoved( ( DataPath )args.OldItem, args.RemovePosition );
      }
      else if( args.Action == DataChangedAction.Add )
      {
        this.ChildDataAdded( ( DataPath )args.NewItem );
      }
      else if( args.Action == DataChangedAction.Reset )
      {
        this.ChildDataReseted();
      }
      else if( args.Action == DataChangedAction.Replace )
      {
        this.ChildDataReplaced( ( DataPath )args.OldItem, ( DataPath )args.NewItem );
      }
      else if( args.Action == DataChangedAction.ItemChanged )
      {
        this.ChildDataItemChanged( args.ItemChangedInfo );
      }
      else
      {
        throw new NotSupportedException();
      }

      base.ChildDataChanged( args );
    }

    // If possible, insert the new item in cache, remove the old item,
    // and update the cache's count values appropriatly.
    // 
    // "haveOldItem/haveNewItem" :
    // 
    // "null" indicates that there may be an [old/new] item.
    // true indicates that there is an [old value/new value] that was [removed/added] in the data source
    // false indicates that there is no [old value/new value] at all. No item was [removed/added] in the data source
    // 
    // "oldIndex/newIndex":  
    // 
    // The value is useless if "haveXXXItem" is "false"
    // "null" indicates that we don't know where the item is located in relation to the cache.
    // int.MinValue indicates that the item is before the cache's first item.
    // int.MaxValue indicates that the item is after the cache's last item.
    // Any other int value refers to the actual [remove/insertion] index in the cache. "haveXXXItem" will be forced to true in this case.
    // 
    // newItem is useless if "haveNewItem" is "false" or if newIndex is null.
    internal void HandleItemChangeCore(
      Nullable<bool> haveOldItem, Nullable<int> oldIndex,
      Nullable<bool> haveNewItem, Nullable<int> newIndex, DataPath newItem )
    {
      // Just to be consistent. Clear any useless values
      if( haveOldItem == false )
        oldIndex = null;

      if( haveNewItem == false )
        newIndex = null;

      //If there is a valid remove index, there is an item to remove
      if( oldIndex != null && oldIndex != int.MinValue && oldIndex != int.MaxValue )
      {
        haveOldItem = true;
      }

      //If there is a valid insert index, there is an item to add.
      if( newIndex != null && newIndex != int.MinValue && newIndex != int.MaxValue )
      {
        haveNewItem = true;
      }

      lock( this.SyncRoot )
      {
        //Add the new item first. 
        //it may keep reference count if the cache is 1 and the removed item is the last one.
        if( newIndex != null && newIndex >= 0 && newIndex <= m_cachedItems.Count )
        {
          m_cachedItems.Insert( newIndex.Value, newItem );

          if( oldIndex != null
            && oldIndex != int.MinValue && oldIndex != int.MaxValue
            && oldIndex >= newIndex )
          {
            oldIndex++;
          }
        }

        //Remove the old item.
        if( oldIndex != null && oldIndex >= 0 && oldIndex < m_cachedItems.Count )
        {
          m_cachedItems.RemoveAt( oldIndex.Value );
        }

        // Update the count information
        RelativeOffset newOffset = null;
        EstimateInt64 newTotalCount = null;

        if( m_cachedItems.Count == 0 )
        {
          this.ClearItemCountEstimates();
        }
        else if( m_firstItemOffset != null )
        {
          if( ( haveOldItem == true && oldIndex == null )
            || ( haveNewItem == true && newIndex == null )
            || ( haveOldItem == null )
            || ( haveNewItem == null ) )
          {
            newOffset = m_firstItemOffset.ToEstimate();
          }
          else
          {
            int offset = 0;
            bool isFirstItemOffsetFromStart = ( m_firstItemOffset.ReferencePosition == ReferencePoint.BeforeFirst );

            if( haveOldItem.GetValueOrDefault( false ) )
            {
              // The item that is being removed isn't in the data source.
              if( ( ( oldIndex.Value < 0 ) && ( this.IsCacheAtStart ) )
                || ( ( oldIndex.Value >= m_cachedItems.Count ) && ( this.IsCacheAtEnd ) ) )
                return;

              bool isBeforeFirst = ( oldIndex.Value < 0 );

              if( isBeforeFirst == isFirstItemOffsetFromStart )
              {
                offset--;
              }
            }

            if( haveNewItem.GetValueOrDefault( false ) )
            {
              bool isBeforeFirst = ( newIndex.Value < 0 );

              if( isBeforeFirst == isFirstItemOffsetFromStart )
              {
                offset++;
              }
            }

            if( offset != 0 )
            {
              newOffset = m_firstItemOffset + offset;
            }
          }
        }

        if( m_totalItemCount != null )
        {
          if( haveOldItem == null || haveNewItem == null )
          {
            newTotalCount = m_totalItemCount.ToEstimate();
          }
          else if( haveOldItem != haveNewItem )
          {
            newTotalCount = ( haveOldItem.Value )
              ? m_totalItemCount - 1
              : m_totalItemCount + 1;
          }
        }

        this.UpdateCountInformation( newOffset, newTotalCount );
      }
    }

    // Return the index where the item should be inserted.
    //
    // int.MinValue will be returned if the item is placed to an unknown offset before
    // the cache's first item.
    //
    // int.MaxValue will be returned if the item is placed to an unknow offset after
    // the cache's last item.
    //
    // If "equal" items are is already inside the cache, the index will be place
    // after the last "equal" item.
    //
    // Execpt for the "Min/Max" Values, the return value should always be ">= 0" and
    // "<= this.CachedItemsCount".
    internal int GetInsertIndex( DataSourceContext context, DataPath item )
    {
      lock( this.SyncRoot )
      {
        if( m_cachedItems.Count == 0 )
          throw new DataInternalException();

        int insertIndex = 0;

        while( insertIndex < m_cachedItems.Count )
        {
          if( m_compareHelper.Compare( context, item, m_cachedItems[ insertIndex ] ) < 0 )
            break;

          insertIndex++;
        }

        // Except when the cache is "at start",
        // an insertIndex of 0, this means that the item 
        // is "somewhere" before the first cache item,
        // not necessarly "right before" the first.
        // That is why I can't insert it in this case.
        // Same concept apply for the last item.

        if( ( insertIndex == 0 ) && ( !this.IsCacheAtStart ) )
        {
          insertIndex = int.MinValue;
        }
        else if( ( insertIndex == m_cachedItems.Count ) && ( !this.IsCacheAtEnd ) )
        {
          insertIndex = int.MaxValue;
        }

        return insertIndex;
      }
    }

    internal int GetRemoveIndex( DataSourceContext context, DataPath item )
    {
      lock( this.SyncRoot )
      {
        if( m_cachedItems.Count == 0 )
          throw new DataInternalException();

        int index = m_cachedItems.IndexOf( item );

        if( index == -1 )
        {
          index = ( m_compareHelper.Compare( context, item, m_cachedItems[ 0 ] ) < 0 ) ? int.MinValue : int.MaxValue;

          Debug.Assert( index != int.MinValue || !this.IsCacheAtStart );
          Debug.Assert( index != int.MaxValue || !this.IsCacheAtEnd );
        }

        return index;
      }
    }

    internal Nullable<int> GetModifiedItemIndexInfo(
      DataSourceContext context,
      ItemChangedInfo itemChangedInfo )
    {
      if( this.CachedItems.Count == 0 )
        throw new DataInternalException();

      lock( this.SyncRoot )
      {
        Nullable<int> index = this.GetModifiedItemIndex( ( DataPath )itemChangedInfo.Target );

        if( index == -1 )
        {
          //Use the obvious. It's not in cache.
          if( this.IsCacheAtStart )
          {
            index = int.MaxValue;
          }
          else if( this.IsCacheAtEnd )
          {
            index = int.MinValue;
          }
        }

        if( index == -1 )
        {
          Nullable<int> relativeIndex = null;
          DataPath item = ( DataPath )itemChangedInfo.Target;

          foreach( SortDescription sortDescription in context.GetCurrentCompleteSortOrder() )
          {
            string propertyName = sortDescription.PropertyName;
            bool descending = ( sortDescription.Direction == ListSortDirection.Descending );

            object firstCacheItemValue = m_itemHelper.GetMemberValue( context, propertyName, m_cachedItems[ 0 ] );

            int compareResult;

            if( !itemChangedInfo.GetIsValueChanged( sortDescription ) )
            {
              object currentSortValue = m_itemHelper.GetMemberValue( context, propertyName, item );

              compareResult = m_compareHelper.Compare( context, propertyName, currentSortValue, firstCacheItemValue );
            }
            else
            {
              object oldValue;
              if( !itemChangedInfo.TryGetOldValue( sortDescription, out oldValue ) )
                break;

              compareResult = m_compareHelper.Compare( context, propertyName, oldValue, firstCacheItemValue );
            }

            if( compareResult != 0 )
            {
              if( descending )
              {
                compareResult = -compareResult;
              }

              relativeIndex = ( compareResult < 0 ) ? int.MinValue : int.MaxValue;
              break;
            }
          }

          index = relativeIndex;
        }

        return index;
      }
    }

    internal virtual int GetModifiedItemIndex( DataPath item )
    {
      lock( this.SyncRoot )
      {
        return m_cachedItems.IndexOf( item );
      }
    }

    protected virtual Nullable<int> FindIndex(
      DataSourceContext context,
      SourcePosition sourcePosition,
      long moveCount,
      int fetchCount )
    {
      if( sourcePosition == null )
        throw new ArgumentNullException( "sourcePosition" );

      if( sourcePosition.IsBeforeFirst )
      {
        if( this.IsCacheAtStart )
          return -1;
      }
      else if( sourcePosition.IsAfterLast )
      {
        lock( this.SyncRoot )
        {
          if( this.IsCacheAtEnd )
            return m_cachedItems.Count;
        }
      }
      else if( sourcePosition is ItemPosition )
      {
        ItemPosition itemPosition = ( ItemPosition )sourcePosition;
        DataPath item = ( DataPath )itemPosition.Item;

        return this.FindIndex( context, item, moveCount, fetchCount );
      }
      else if( sourcePosition is SortPosition )
      {
        SortPosition sortPosition = ( SortPosition )sourcePosition;

        return this.FindIndex( context, sortPosition, moveCount, fetchCount );
      }

      return null;
    }

    protected virtual Nullable<int> FindIndex(
      DataSourceContext context,
      DataPath targetItem,
      long moveCount,
      int fetchCount )
    {
      lock( this.SyncRoot )
      {
        if( ( m_cachedItems.Count == 0 )
          || ( !this.MatchCurrentContext( context ) ) )
          return null;

        int index = m_cachedItems.IndexOf( targetItem );

        if( index >= 0 )
          return index;

        index = m_cachedItems.BinarySearch(
                  targetItem,
                  new ItemComparer( context, m_compareHelper ) );

        // The item was found.
        if( index >= 0 )
          return index;

        index = ~index;

        return this.AdjustFindIndex( index, moveCount, fetchCount, true );
      }
    }

    protected virtual Nullable<int> FindIndex(
      DataSourceContext context,
      SortPosition sortPosition,
      long moveCount,
      int fetchCount )
    {
      lock( this.SyncRoot )
      {
        if( ( m_cachedItems.Count == 0 )
          || ( !this.MatchCurrentContext( context ) ) )
          return null;

        SortPositionComparer comparer = new SortPositionComparer( context, m_compareHelper, sortPosition );
        int index = m_cachedItems.BinarySearch( comparer.Target, comparer );
        bool isItemPrecise = ( context.GetCurrentCompleteSortOrder().Count() == sortPosition.SortValues.Count );

        // The item was not found.
        if( index < 0 )
          return this.AdjustFindIndex( ~index, moveCount, fetchCount, isItemPrecise );

        if( isItemPrecise )
          return index;

        if( sortPosition.StartPosition == StartPosition.Before )
        {
          if( moveCount < 0 )
            return index + 1;

          if( ( moveCount == 0 ) && ( fetchCount < 0 ) )
            return index - 1;
        }
        else
        {
          if( moveCount > 0 )
            return index - 1;
        }

        return index;
      }
    }

    protected Nullable<int> AdjustFindIndex(
      int index,
      long moveCount,
      int fetchCount,
      bool isItemPrecise )
    {
      Debug.Assert( index >= 0 && index <= m_cachedItems.Count );

      // The desired position is prior to the cache.
      if( index == 0 )
      {
        // Since the cache doesn't contains the start of the source, there is no
        // way to find out if the position would have been in cache.
        if( !this.IsCacheAtStart )
          return null;

        if( !isItemPrecise )
        {
          if( moveCount < 0 )
            return 0;

          if( ( moveCount == 0 ) && ( fetchCount < 0 ) )
            return -1;

          return null;
        }
      }

      // The desired position is after the cache.
      int itemsCount = m_cachedItems.Count;
      if( index == itemsCount )
      {
        // Since the cache doesn't contains the end of the source, there is no
        // way to find out if the position would have been in cache.
        if( !this.IsCacheAtEnd )
          return null;

        if( !isItemPrecise )
        {
          if( moveCount == 0 )
          {
            if( fetchCount >= 0 )
              return itemsCount;

            return itemsCount - 1;
          }
          else if( moveCount > 0 )
            return itemsCount - 1;

          return null;
        }
      }

      // Adjust the index to take into account the operation that will be done.
      if( ( moveCount > 0 ) || ( moveCount == 0 && fetchCount < 0 ) )
        return index - 1;

      return index;
    }

    protected override void Dispose( bool disposing )
    {
      m_disposed = true;

      if( disposing )
      {
        this.FlushCache( 0, false );
      }

      base.Dispose( disposing );
    }

    protected virtual void TrimCache(
      int removeCount,
      int topLimitIndex,
      out int removeFromStart,
      out int removeFromEnd )
    {
      removeFromStart = 0;
      removeFromEnd = 0;

      removeFromStart = Math.Min( topLimitIndex, removeCount );
      removeFromEnd = removeCount - removeFromStart;
    }

    private bool FetchCacheData(
      int startIndex,
      long moveCount,
      int fetchCount,
      out long actualMove,
      out IList<DataPath> data,
      out SourcePosition endPosition,
      out RelativeOffset endPositionOffset,
      out EstimateInt64 totalCount )
    {
      Debug.Assert( m_cachedItems.Count > 0 || this.IsCacheComplete );
      Debug.Assert( startIndex >= -1 && startIndex <= m_cachedItems.Count );

      data = null;
      endPositionOffset = null;
      totalCount = m_totalItemCount;
      endPosition = null;

      bool isCacheAtStart = this.IsCacheAtStart;
      bool isCacheAtEnd = this.IsCacheAtEnd;

      long index = startIndex + moveCount;
      long reachedIndex = index;
      bool ret = true;

      if( isCacheAtEnd && isCacheAtStart )
      {
        totalCount = new EstimateInt64( m_cachedItems.Count, false );
      }

      if( startIndex < 0 && moveCount <= 0 && !isCacheAtStart )
      {
        actualMove = 0;
        endPosition = null;
        return true;
      }

      if( startIndex >= m_cachedItems.Count && moveCount >= 0 && !isCacheAtEnd )
      {
        actualMove = 0;
        endPosition = null;
        return true;
      }

      int lowLimitIndex = ( isCacheAtStart ) ? -1 : 0;
      int upLimitIndex = ( isCacheAtEnd ) ? m_cachedItems.Count : m_cachedItems.Count - 1;

      int endIndex = Convert.ToInt32( Math.Max( lowLimitIndex, Math.Min( upLimitIndex, startIndex + moveCount ) ) );
      actualMove = endIndex - startIndex;

      if( endIndex == -1 )
      {
        Debug.Assert( isCacheAtStart );

        endPosition = SourcePosition.BeforeFirst;
        ret = false;
      }
      else if( endIndex == m_cachedItems.Count )
      {
        Debug.Assert( isCacheAtEnd );

        endPosition = SourcePosition.AfterLast;
        ret = false;
      }

      if( ret )
      {
        if( actualMove == moveCount )
        {
          Debug.Assert( endIndex - startIndex == moveCount );

          if( fetchCount == 0 )
          {
            data = new List<DataPath>();
            endPosition = new ItemPosition( m_cachedItems[ endIndex ] );
          }
          else
          {
            int beginIndex = endIndex;
            int fetchUnit = DataUtils.GetUnit( fetchCount );
            endIndex = Math.Max( 0, Math.Min( m_cachedItems.Count - 1, beginIndex + fetchCount - fetchUnit ) );


            List<DataPath> retData = m_cachedItems.GetRange(
                                Math.Min( endIndex, beginIndex ),
                                Math.Abs( endIndex - beginIndex ) + 1 );

            if( fetchUnit > 0 )
            {
              ret = ( retData.Count == Math.Abs( fetchCount ) || !isCacheAtEnd );
            }
            else
            {
              ret = ( retData.Count == Math.Abs( fetchCount ) || !isCacheAtStart );
              retData.Reverse();
            }

            if( !ret )
            {
              endPosition = ( fetchUnit > 0 )
                ? SourcePosition.AfterLast
                : SourcePosition.BeforeFirst;

              endIndex += fetchUnit;
            }
            else
            {
              endPosition = new ItemPosition( retData[ retData.Count - 1 ] );
            }

            data = retData;
          }
        }
        else
        {
          endPosition = new ItemPosition( m_cachedItems[ endIndex ] );
        }
      }

      endPositionOffset = DataUtils.CalculateRelativeOffset( m_firstItemOffset, endIndex );

      return ret;
    }

    private bool MergeResult( DataSourceContext context, JumpMoveAndFetchResult<DataPath> result )
    {
      if( !this.MatchCurrentContext( context ) )
        return false;

      EstimateInt64 fetchedItemsStartIndex = null;
      RelativeOffset firstItemOffset = null;


      this.ExtractIndexes( context, result, out fetchedItemsStartIndex, out firstItemOffset );

      if( ( fetchedItemsStartIndex == null || fetchedItemsStartIndex.IsEstimate )
        && ( result.FetchedItems != null && result.FetchedItems.Count > 0 ) )
      {
        //By no means can we merge the actual fetched items into the cache. Just override the cache with 
        //the recently fetched data.
        this.ReplaceCache( result );
        return true;
      }

      //Merge count information
      this.UpdateCountInformation( firstItemOffset, result.TotalCount );

      //Merge items
      if( result.FetchedItems != null && result.FetchedItems.Count > 0 )
      {
        Debug.Assert( fetchedItemsStartIndex != null && !fetchedItemsStartIndex.IsEstimate, "This case is supposed to be handled by ReplaceCache" );

        List<DataPath> data = result.FetchedItems.ToList();
        int insertionIndex = Convert.ToInt32( fetchedItemsStartIndex.Value );

        //Set the data to be merge in the appropriate orientation.
        if( !result.IsFetchingForward() )
        {
          insertionIndex -= ( result.FetchedItems.Count - 1 );
          data.Reverse();
        }

        this.MergeItems( insertionIndex, data );
      }

      return true;
    }

    protected void ExtractIndexes(
      DataSourceContext context,
      JumpMoveAndFetchResult<DataPath> result,
      out EstimateInt64 fetchedItemStartIndex,
      out RelativeOffset firstItemOffset )
    {
      fetchedItemStartIndex = null;
      firstItemOffset = null;

      lock( this.SyncRoot )
      {
        if( ( m_cachedItems.Count == 0 ) || ( !this.MatchCurrentContext( context ) ) )
          return;

        bool haveFetchItems = ( result.FetchedItems != null && result.FetchedItems.Count > 0 );
        Nullable<int> referenceIndex = null;
        EstimateInt64 operationOffset = null;

        if( haveFetchItems )
        {
          //Try to identify using first item
          int firstIndex = m_cachedItems.IndexOf( result.FetchedItems.First() );

          if( firstIndex >= 0 )
          {
            referenceIndex = firstIndex;
            operationOffset = result.GetFetchDisplacement();
            fetchedItemStartIndex = firstIndex;
          }
        }

        if( !referenceIndex.HasValue && haveFetchItems && result.FetchedItems.Count > 1 )
        {
          int lastIndex = m_cachedItems.IndexOf( result.FetchedItems.Last() );

          if( lastIndex >= 0 )
          {
            referenceIndex = lastIndex;
            operationOffset = ( !result.Result ) ? result.GetFetchUnit() : 0;
            fetchedItemStartIndex = -( ( result.FetchedItems.Count - 1 ) * result.GetFetchUnit() ) + lastIndex;
          }
        }

        if( !referenceIndex.HasValue )
        {
          //Try to get a reference with the EndPosition
          if( result.EndPositionObject is ItemPosition )
          {
            // Fallback direction is used if the end position is place "between" two cache items.
            // This mean that the cache is "out of sync" with the source.
            int fallbackDirection =
              ( result.ExpectedFetchCount != 0 )
              ? -result.GetFetchUnit()
              : -result.GetMoveUnit();

            referenceIndex = this.FindIndex( context, result.EndPositionObject, 0, fallbackDirection );

            if( referenceIndex.HasValue )
            {
              operationOffset = 0;
              if( haveFetchItems && fetchedItemStartIndex != null )
              {
                Debug.Assert( fetchedItemStartIndex.Value == ( referenceIndex - result.GetFetchDisplacement() ) );
                fetchedItemStartIndex = referenceIndex - result.GetFetchDisplacement();
              }
            }
          }
        }

        if( !referenceIndex.HasValue && ( result.ActualMoveCount.HasValue || Math.Abs( result.ExpectedMoveCount ) == 1 ) )
        {
          referenceIndex = this.FindIndex( context, result.SourcePosition, result.ExpectedMoveCount, result.ExpectedFetchCount );

          if( referenceIndex.HasValue )
          {
            Nullable<long> actualMove = result.ActualMoveCount;

            if( actualMove == null && Math.Abs( result.ExpectedMoveCount ) == 1 )
            {
              actualMove = result.ExpectedMoveCount;
            }

            if( actualMove != null )
            {
              bool isApproxMove = result.ExpectedMoveCount != 0 && result.ApproximateMove;
              operationOffset = new EstimateInt64( ( actualMove.Value + result.GetFetchDisplacement() ), isApproxMove );

              if( !isApproxMove && result.FetchedItems != null )
              {
                fetchedItemStartIndex = referenceIndex + result.ActualMoveCount.Value;
              }
            }
          }
        }

        if( referenceIndex.HasValue && operationOffset != null && result.EndPositionOffset != null )
        {
          long correction = ( referenceIndex.Value + operationOffset.Value );
          bool isEstimate = operationOffset.IsEstimate | result.EndPositionOffset.IsEstimate;

          if( result.EndPositionOffset.ReferencePosition == ReferencePoint.BeforeFirst )
          {
            correction = -correction;
          }

          firstItemOffset = new RelativeOffset(
              new EstimateInt64( result.EndPositionOffset.Value + correction, isEstimate ),
              result.EndPositionOffset.ReferencePosition );
        }
      }
    }

    private void ReplaceCache( JumpMoveAndFetchResult<DataPath> result )
    {
      bool haveFetchItems = ( result.FetchedItems != null && result.FetchedItems.Count > 0 );

      m_cachedItems.Clear();

      this.ClearItemCountEstimates();

      if( result.TotalCount != null )
      {
        m_totalItemCount = result.TotalCount;
      }

      if( !haveFetchItems )
      {
        return;
      }

      if( result.IsFetchingForward() )
      {
        m_cachedItems.AddRange( result.FetchedItems );

        m_firstItemOffset = DataUtils.CalculateRelativeOffset(
          result.EndPositionOffset,
          -result.GetFetchDisplacement() );
      }
      else
      {
        m_cachedItems.AddRange( result.FetchedItems.Reverse() );

        m_firstItemOffset = result.EndPositionOffset;

        if( !result.Result )
        {
          this.AdjustFirstItemOffset( 1 );
        }
      }
    }

    private void MergeItems( int startInsertionIndex, List<DataPath> data )
    {
      if( data == null )
        throw new ArgumentNullException( "data" );

      if( data.Count == 0 )
        return;

      int endInsertionIndex = startInsertionIndex + data.Count;
      int initialCacheStartIndex = 0;
      int initialCacheEndIndex = m_cachedItems.Count;
      int finalCacheStartIndex;
      int finalCacheEndIndex;

      if( endInsertionIndex <= -1 || startInsertionIndex > m_cachedItems.Count )
      {
        m_cachedItems.Clear();
        m_cachedItems.AddRange( data );

        finalCacheStartIndex = startInsertionIndex;
        finalCacheEndIndex = endInsertionIndex;
      }
      else
      {
        finalCacheStartIndex = Math.Min( startInsertionIndex, 0 );
        finalCacheEndIndex = Math.Max( endInsertionIndex, m_cachedItems.Count );

        //Replace overlap...
        int maxStartIndex = Math.Max( startInsertionIndex, 0 );
        int minEndIndex = Math.Min( endInsertionIndex, m_cachedItems.Count );

        for( int i = maxStartIndex; i < minEndIndex; i++ )
        {
          m_cachedItems[ i ] = data[ i - startInsertionIndex ];
        }

        // Append some items at the end of the cache.
        // This operation must be done before the insertion at the begin
        // of the cache.
        if( endInsertionIndex > m_cachedItems.Count )
        {
          int rangeStartIndex = m_cachedItems.Count - startInsertionIndex;
          int rangeLength = endInsertionIndex - m_cachedItems.Count;

          m_cachedItems.AddRange( data.GetRange( rangeStartIndex, rangeLength ) );
        }

        // Insert any remaining items at the start of the cache.
        if( startInsertionIndex < 0 )
        {
          m_cachedItems.InsertRange( 0, data.GetRange( 0, -startInsertionIndex ) );
        }
      }

      this.AdjustFirstItemOffset( finalCacheStartIndex - initialCacheStartIndex );
    }

    private void TrimCache( int topLimitIndex )
    {
      if( m_cachedItems.Count <= this.CacheSize )
        return;

      int removeCount = m_cachedItems.Count - this.CacheSize;
      int removeFromStart;
      int removeFromEnd;

      this.TrimCache(
        removeCount,
        topLimitIndex,
        out removeFromStart,
        out removeFromEnd );

      Debug.Assert(
        removeFromStart >= 0
        && removeFromEnd >= 0
        && removeFromStart + removeFromEnd == removeCount );

      int currentTime = Environment.TickCount;

      if( removeFromStart > 0 )
      {
        m_cachedItems.RemoveRange( 0, removeFromStart );

        this.AdjustFirstItemOffset( removeFromStart );
      }

      if( removeFromEnd > 0 )
      {
        m_cachedItems.RemoveRange( m_cachedItems.Count - removeFromEnd, removeFromEnd );
      }

      m_cachedItems.TrimExcess();
    }

    protected void AdjustFirstItemOffset( long referenceOffset )
    {
      lock( this.SyncRoot )
      {
        m_firstItemOffset = DataUtils.CalculateRelativeOffset( m_firstItemOffset, referenceOffset );
      }
    }

    private void ClearItemCountEstimates()
    {
      m_firstItemOffset = null;
    }

    internal void FlushCache( int startingIndex, bool towardStart )
    {
      if( startingIndex < 0 )
        throw new ArgumentOutOfRangeException( "startingIndex", "startingIndex must be greater than or equal to zero." );

      lock( this.SyncRoot )
      {
        if( !towardStart )
        {
          if( m_cachedItems.Count > startingIndex )
          {
            int removeItemCount = m_cachedItems.Count - startingIndex;

            m_cachedItems.RemoveRange( startingIndex, removeItemCount );

            if( startingIndex == 0 )
            {
              this.ClearItemCountEstimates();
            }
          }
        }
        else
        {
          int removeItemCount = Math.Min( m_cachedItems.Count, startingIndex + 1 );

          m_cachedItems.RemoveRange( 0, removeItemCount );

          if( m_cachedItems.Count == 0 )
          {
            this.ClearItemCountEstimates();
          }
          else
          {
            this.AdjustFirstItemOffset( removeItemCount );
          }
        }
      }
    }

    internal void FlushCache()
    {
      this.FlushCache( 0, false );
    }

    #region ICachingEnumerator Members

    int ICachingEnumerator.CacheSize
    {
      get
      {
        return this.CacheSize;
      }
    }

    void ICachingEnumerator.SetCacheSize( int size )
    {
      this.SetCacheSize( size, 0d );
    }

    public void SetCacheSize( int size, double topTrimRatio )
    {
      if( topTrimRatio < 0 || topTrimRatio > 1 )
        throw new ArgumentOutOfRangeException( "topTrimRatio", "topTrimRation must be greater than or equal to zero and less than or equal to one." );

      lock( this.SyncRoot )
      {
        int removeCount = Math.Max( 0, m_cachedItems.Count - this.CacheSize );
        int removeFromStart = ( int )( removeCount * topTrimRatio );

        this.SetCacheSize( size, removeFromStart );
      }
    }

    public void SetCacheSize( int size, SourcePosition topLimitTrim )
    {
      lock( this.SyncRoot )
      {
        Nullable<int> topLimitIndex = null;

        if( topLimitTrim != null )
        {
          DataSourceContext context = this.GetCurrentContext();

          topLimitIndex = this.FindIndex( context, topLimitTrim, 0, 1 );
        }

        this.SetCacheSize( size, topLimitIndex.GetValueOrDefault( 0 ) );
      }
    }

    private void SetCacheSize( int size, int topLimitTrim )
    {
      if( size < 0 )
        throw new ArgumentOutOfRangeException( "size", "size must be greater than or equal to zero." );

      lock( this.SyncRoot )
      {
        int cacheSize = this.CacheSize;

        if( cacheSize != size )
        {
          this.CacheSize = size;

          if( cacheSize > size )
          {
            this.TrimCache( topLimitTrim );
          }
        }
      }
    }

    #endregion

    #region Private Fields

    private bool m_disposed; //false

    #endregion

    #region CacheJumpAsyncResult Nested Type

    private class CacheJumpAsyncResult : JumpMoveAndFetchAsyncResult
    {
      internal CacheJumpAsyncResult(
        Guid callId,
        AsyncCallback userCallback,
        object asyncState,
        JumpMoveAndFetchParameters parameters )
        : base(
          callId,
          userCallback,
          asyncState,
          parameters )
      {
      }

      internal IList<DataPath> CacheData
      {
        get;
        set;
      }
      internal long CacheMove
      {
        get;
        set;
      }
      internal RelativeOffset CacheEndPositionOffset
      {
        get;
        set;
      }
      internal EstimateInt64 CacheTotalCount
      {
        get;
        set;
      }
    }

    #endregion

    #region CachePositionState Enum Nested Type

    private enum CachePositionState
    {
      Maybe,
      Yes,
      No
    };

    #endregion

    #region ItemComparer Nested Type

    private class ItemComparer : IComparer<DataPath>
    {
      internal ItemComparer( DataSourceContext context, IContextualCompareHelper comparer )
      {
        if( context == null )
          throw new ArgumentNullException( "context" );

        if( comparer == null )
          throw new ArgumentNullException( "comparer" );

        m_context = context;
        m_comparer = comparer;
      }

      public int Compare( DataPath x, DataPath y )
      {
        return m_comparer.Compare( m_context, x, y );
      }

      private readonly DataSourceContext m_context;
      private readonly IContextualCompareHelper m_comparer;
    }

    #endregion

    #region SortPositionComparer Nested Type

    private class SortPositionComparer : IComparer<DataPath>
    {
      private static readonly DataPath FakeTarget = new DataPath( new DataItem[ 0 ] );

      internal SortPositionComparer(
        DataSourceContext context,
        IContextualCompareHelper comparer,
        SortPosition position )
      {
        if( context == null )
          throw new ArgumentNullException( "context" );

        if( comparer == null )
          throw new ArgumentNullException( "comparer" );

        if( position == null )
          throw new ArgumentNullException( "position" );

        m_context = context;
        m_comparer = comparer;
        m_position = position;
      }

      public DataPath Target
      {
        get
        {
          return SortPositionComparer.FakeTarget;
        }
      }

      public int Compare( DataPath x, DataPath y )
      {
        if( object.ReferenceEquals( x, this.Target ) )
          return m_comparer.Compare( m_context, m_position, y );

        if( object.ReferenceEquals( y, this.Target ) )
          return m_comparer.Compare( m_context, x, m_position );

        return m_comparer.Compare( m_context, x, y );
      }

      private readonly DataSourceContext m_context;
      private readonly IContextualCompareHelper m_comparer;
      private readonly SortPosition m_position;
    }

    #endregion
  }
}
